//763 划分字母区间
/*
字符串 `S` 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表

输入：S = "ababcbacadefegdehijhklij" //ababcbaca defegde hijhklij
输出：[9,7,8]
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中

分析：由于同一个字母只能出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置
*/
//
vector<int> partitionLabels(string S)
{
	int last[26]; //存放26个字母 最后一次出现的位置下标
	int length = S.size();

	//
	for (int i = 0; i < length; i++)
	{
		last[S[i] - 'a'] = i; //S[i] - 'a' 表示字母表的下标，last表示字母表
	}

	vector<int> partition;
	int start = 0, end = 0;
	for (int i = 0; i < length; i++)
	{
		end = max(end, last[S[i] - 'a']); //
		//当访问到下标 end\textit{end}end 时，当前片段访问结束，当前片段的下标范围是 end-start，长度为 end−start+1

		if (i == end)
		{
			partition.push_back(end - start + 1); //片区
			start = end + 1;					  //片区长度
		}
	}
	return partition;
}